#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if (nums.empty())
            return 0;
        vector<int> indices(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            indices[i] = i;
        }
        return sorthelper(nums, indices, 0, nums.size() - 1);
    }

private:
    int sorthelper(vector<int>& nums, vector<int>& indices, int left,
        int right) {
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        int count = sorthelper(nums, indices, left, mid) +
            sorthelper(nums, indices, mid + 1, right);
        count += merge(nums, indices, left, mid, right);
        return count;
    }
    int merge(vector<int>& nums, vector<int>& indices, int left, int mid,
        int right) {
        vector<int> temp(right - left + 1);
        int countreverse = 0;
        int p = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (p <= right && (long long)nums[indices[i]] > 2LL * (long long)nums[indices[p]]) {
                p++;
            }
            countreverse += (p - (mid + 1));
        }
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[indices[i]] <= nums[indices[j]]) {
                temp[k++] = indices[i++];
            }
            else {
                temp[k++] = indices[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = indices[i++];
        }
        while (j <= right) {
            temp[k++] = indices[j++];
        }
        for (int idx = 0; idx < k; idx++) {
            indices[left + idx] = temp[idx];
        }
        return countreverse;
    }
};
class Solution {
public:
    static const int MAXN = 50001;
    int help[MAXN];

    int reversePairs(vector<int>& nums) {
        if (nums.empty())
            return 0;
        return sorthelper(nums, 0, nums.size() - 1);
    }

private:
    int sorthelper(vector<int>& nums, int left, int right) {
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        return sorthelper(nums, left, mid) +
            sorthelper(nums, mid + 1, right) +
            merge(nums, left, mid, right);
    }

    int merge(vector<int>& nums, int left, int mid, int right) {
        int countreverse = 0;
        int p = mid + 1;

        for (int i = left; i <= mid; i++) {
            while (p <= right && (long long)nums[i] > 2LL * (long long)nums[p]) {
                p++;
            }
            countreverse += (p - (mid + 1));
        }

        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                help[k++] = nums[i++];
            }
            else {
                help[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            help[k++] = nums[i++];
        }
        while (j <= right) {
            help[k++] = nums[j++];
        }

        for (int idx = left; idx <= right; idx++) {
            nums[idx] = help[idx];
        }

        return countreverse;
    }
};